package com.leetcode.algorithm.y22.m09.w3;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 988. 从叶结点开始的最小字符串
 * 
 * https://leetcode.cn/problems/smallest-string-starting-from-leaf/
 * 
 * @author jie.deng
 *
 */
class Question0988Solution01 {

	public String smallestFromLeaf(TreeNode root) {
		List<String> strs = new ArrayList<>();
		Deque<Character> queue = new ArrayDeque<>();
		dfs(root, strs, queue);
		Collections.sort(strs);
		return strs.get(0);
	}

	// DFS 先序遍历
	// 从根节点到叶子节点的路径
	private void dfs(TreeNode node, List<String> result, Deque<Character> queue) {
		// 当前层逻辑
		queue.offerLast(Character.valueOf((char) (node.val + 'a')));

		if (node.left == null && node.right == null) {
			// 递归终止条件
			StringBuilder builder = new StringBuilder();
			Iterator<Character> iter = queue.iterator();
			while (iter.hasNext()) {
				builder.append(iter.next());
			}
			result.add(builder.reverse().toString());
		} else {
			// 递归调用
			if (node.left != null) {
				dfs(node.left, result, queue);
			}
			if (node.right != null) {
				dfs(node.right, result, queue);
			}
		}

		// 回溯
		queue.pollLast();
	}

}